package com.lw.leetcode.tree;

import lombok.ToString;

/**
 * @Author liw
 * @Date 2021/4/16 9:58
 * @Version 1.0
 */

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode getInstance() {

        //      1
        //     / \
        //   2    3
        //  / \    \
        // 4  5     6
        //   / \
        //  7  8
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);
        TreeNode h = new TreeNode(8);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        e.left = g;
        e.right = h;
        return a;
    }


    public static TreeNode getInstance2() {

        //      4
        //     / \
        //   2    5
        //  / \    \
        // 1  3     6

        TreeNode a = new TreeNode(4);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(5);
        TreeNode d = new TreeNode(1);
        TreeNode e = new TreeNode(3);
        TreeNode f = new TreeNode(6);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        return a;
    }

    public static TreeNode getInstance3() {

        //      5
        //     / \
        //   2    -2

        TreeNode a = new TreeNode(5);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(-2);

        a.left = b;
        a.right = c;

        return a;
    }
    public static TreeNode getInstance4() {

        //      5
        //     / \
        //   4    5
        //  / \    \
        // 1  1     5

        TreeNode a = new TreeNode(5);
        TreeNode b = new TreeNode(4);
        TreeNode c = new TreeNode(5);
        TreeNode d = new TreeNode(1);
        TreeNode e = new TreeNode(1);
        TreeNode f = new TreeNode(5);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        return a;
    }

    // [1,null,2,3,4,null,null,5,6]
    public static TreeNode getInstance5() {

        //      1
        //       \
        //        2
        //       / \
        //      3   4
        //         / \
        //        5  6
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        a.right = b;
        b.left = c;
        b.right = d;
        d.left = e;
        d.right = f;
        return a;
    }


    // [2,3,1,3,1,null,1]
    public static TreeNode getInstance6() {

        //      2
        //     / \
        //   3    1
        //  / \    \
        // 3  1     1

        TreeNode a = new TreeNode(2);
        TreeNode b = new TreeNode(3);
        TreeNode c = new TreeNode(1);
        TreeNode d = new TreeNode(3);
        TreeNode e = new TreeNode(1);
        TreeNode f = new TreeNode(1);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        return a;
    }
    public static TreeNode getInstance7() {

        //     0
        //    / \
        //   4   5
        //  / \   \
        // 1   3   1

        TreeNode a = new TreeNode(0);
        TreeNode b = new TreeNode(4);
        TreeNode c = new TreeNode(5);
        TreeNode d = new TreeNode(1);
        TreeNode e = new TreeNode(3);
        TreeNode f = new TreeNode(1);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        return a;
    }
    public static TreeNode getInstance8() {

        //       4
        //      /
        //     1
        //    /
        //   2
        //  /
        // 3

        TreeNode a = new TreeNode(4);
        TreeNode b = new TreeNode(1);
        TreeNode c = new TreeNode(2);
        TreeNode d = new TreeNode(3);
        a.left = b;
        b.left = c;
        c.left = d;
        return a;
    }
    public static TreeNode getInstance9() {

        //     0
        //    / \
        //   2   1
        //      /
        //     3

        TreeNode a = new TreeNode(0);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(1);
        TreeNode d = new TreeNode(3);
        a.left = b;
        a.right = c;
        c.left = d;

        return a;
    }

    public static TreeNode getInstance10() {

        //       3
        //    /    \
        //   1     4
        //  / \    /
        // 0   2  2

        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(1);
        TreeNode c = new TreeNode(4);
        TreeNode d = new TreeNode(0);
        TreeNode e = new TreeNode(2);
        TreeNode f = new TreeNode(2);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        return a;
    }


    public static TreeNode getInstance11() {

        //         1
        //      /    \
        //    4       3
        //  /  \    /  \
        // 2   4  2    5
        //           / \
        //          4  6
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(4);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(2);
        TreeNode e = new TreeNode(4);
        TreeNode f = new TreeNode(2);
        TreeNode g = new TreeNode(5);
        TreeNode h = new TreeNode(4);
        TreeNode i = new TreeNode(6);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        g.left = h;
        g.right = i;
        return a;
    }

    public static TreeNode getInstance12() {


        // 1
        //  \
        //   2
        //    \
        //     3
        //      \
        //       4

        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        a.right = b;
        b.right = c;
        c.right = d;
        return a;
    }

    public static TreeNode getInstance13() {


        // 1
        //  \
        //   2
        //    \
        //     0
        //      \
        //       3

        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(0);
        TreeNode d = new TreeNode(3);
        a.right = b;
        b.right = c;
        c.right = d;
        return a;
    }

    public static TreeNode getInstance14() {

        //       1
        //    /
        //   3
        //    \
        //     2

        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(3);
        TreeNode e = new TreeNode(2);
        a.left = b;
        b.right = e;
        return a;
    }



    public static TreeNode getInstance15() {


        // 1
        //  \
        //   2
        //    \
        //     3
        //      \
        //       4
        //        \
        //         5
        //          \
        //           6

        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        a.right = b;
        b.right = c;
        c.right = d;
        d.right = e;
        e.right = f;
        return a;
    }





    public static TreeNode getInstance16() {

        //         2
        //      /
        //    1
        TreeNode a = new TreeNode(2);
        TreeNode b = new TreeNode(1);
        a.left = b;
        return a;
    }



    public static TreeNode getInstance17() {

        //         3
        //      /    \
        //    2       5
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(5);
        a.left = b;
        a.right = c;
        return a;
    }


    public static TreeNode getInstance18() {

        //         5
        //      /
        //    4
        TreeNode a = new TreeNode(5);
        TreeNode b = new TreeNode(4);
        a.left = b;
        return a;
    }


    public static TreeNode getInstance20() {

        //         0
        //      /    \
        //    0       0
        TreeNode a = new TreeNode(0);
        TreeNode b = new TreeNode(0);
        TreeNode c = new TreeNode(0);
        TreeNode d = new TreeNode(0);
        TreeNode e = new TreeNode(0);
        TreeNode f = new TreeNode(0);
        TreeNode g = new TreeNode(0);
        a.left = b;
        a.right = c;
        b.left = d;
        c.right = e;
        e.right = f;
        return a;
    }

    public static TreeNode getInstance21() {

        //         1
        //      /    \
        //    0       0
        //  /  \    /  \
        // 1   0  1
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(0);
        TreeNode c = new TreeNode(0);
        TreeNode d = new TreeNode(1);
        TreeNode e = new TreeNode(0);
        TreeNode f = new TreeNode(1);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        return a;
    }


    @Override
    public String toString() {
        return "{" +
                "val=" + val +
                ", left =" + left +
                ", right=" + right +
                '}';
    }
}
